package report4;

import report4.classes.Page;

import java.util.*;

/**
 * @author zouran
 * createDate：2023/5/17  20:47
 */
public class Pagination {
    //总的访问记录
    private final List<Page> pageList = new ArrayList<>();
    //当前内存页面状态
    private final List<Integer> list = new ArrayList<>();
    //clock算法下访问位
    private final boolean[] request = new boolean[100];
    //物理块个数
    private final Integer count;
    //访问序列长度
    private final Integer length;
    //获取总的缺页次数
    private Integer sumMiss = 0;
    //当前指针所指位置
    private Integer currentPointer = 0;
    //页面访问序列
    private List<Integer> requestList = new ArrayList<>();

    Pagination(Integer length, Integer count) {
        this.length = length;
        this.count = count;
        for (int i = 0; i < count; i++) {
            list.add(-1);
        }
    }

    Pagination(Integer length, Integer count, List<Integer> inlist) {
        this.length = length;
        this.count = count;
        for (int i = 0; i < count; i++) {
            list.add(-1);
        }
        this.requestList = new ArrayList<>(inlist);
    }

    //随机生成访问序列
    public List<Integer> randomRequestList() {
        for (int i = 0; i < length; i++) {
            requestList.add(new Random().nextInt(5));
        }
        return requestList;
    }

    //判断是否缺页
    private boolean isMissingPage(Integer target) {
        for (Integer integer : list) {
            if (Objects.equals(integer, target))
                return false;
        }
        return true;
    }

    //当前块数是否已满
    private boolean currentIsFull() {
        for (Integer integer : list) {
            if (integer == -1) return false;
        }
        return true;
    }

    //当前块数未满时直接加入
    private void addPage(Integer pageNumber) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) == -1) {
                list.set(i, pageNumber);
                break;
            }
        }
    }

    //clock算法下寻找替换值
    public Integer findIndex() {
        for (int i = currentPointer; i < count; i++) {
            if (!request[i]) {
                return i;
            }
        }
        for (int i = 0; i < currentPointer; i++) {
            if (!request[i]) {
                return i;
            }
        }
        //访问位全部置0
        Arrays.fill(request, false);
        for (int i = currentPointer; i < count; i++) {
            if (!request[i]) {
                return i;
            }
        }
        return 0;
    }

    //OPT算法寻找后面最优替换项，返回被替换值
    //LRU算法则是往前找
    public Integer findBestReplace(int begin, String option) {
        Map<Integer, Integer> map = new HashMap<>();//记录距离
        Map<Integer, Integer> map1 = new HashMap<>();//记录是否第一个
        for (Integer integer : list) {
            //初始化距离
            map.put(integer, Integer.MAX_VALUE);
            map1.put(integer, 0);
        }
        if (Objects.equals(option, "OPT")) {
            for (Integer integer : list) {
                for (int i = begin + 1; i < requestList.size(); i++) {
                    if (Objects.equals(integer, requestList.get(i))) {
                        if (map1.get(integer) == 0) {
                            map1.replace(integer, 1);
                            //计算距离
                            map.replace(integer, Math.abs(begin - i));
                        }
                        break;
                    }
                }
            }
        } else if (Objects.equals(option, "LRU")) {
            for (Integer integer : list) {
                for (int i = begin - 1; i >= 0; i--) {
                    if (Objects.equals(integer, requestList.get(i))) {
                        if (map1.get(integer) == 0) {
                            map1.replace(integer, 1);
                            map.replace(integer, Math.abs(i - begin));
                        }
                        break;
                    }
                }
            }
        }
        int maxDistance = 0;
        int max = 0;
        //求最大距离
        for (Integer integer : map.keySet()) {
//            System.out.println(integer+" "+map.get(integer));
            if (map.get(integer) > maxDistance) {
                max = integer;
                maxDistance = map.get(integer);
            }
        }
        //最后一个时直接替换第一个
        return max;
    }

    //OPT算法或者LRU算法
    public void OPTorLRU(String option) {
        for (int i = 0; i < requestList.size(); i++) {
            if (isMissingPage(requestList.get(i))) {
                if (currentIsFull()) {
                    int value = findBestReplace(i, option);
//                    System.out.println(value);
                    for (int j = 0; j < list.size(); j++) {
                        if (list.get(j) == value) {
                            list.set(j, requestList.get(i));
                            break;
                        }
                    }
                } else {
                    addPage(requestList.get(i));
                }
                sumMiss++;
                pageList.add(new Page(new ArrayList<>(list), requestList.get(i), true));
            } else {
                pageList.add(new Page(new ArrayList<>(list), requestList.get(i), false));
            }
        }
        print(option);
    }

    //FIFO算法
    public void FIFO() {
        for (Integer integer : requestList) {
            if (isMissingPage(integer)) {
                if (currentIsFull()) {
                    //替换指针所指位置值
                    list.set(currentPointer, integer);
                } else {
                    addPage(integer);
                }
                sumMiss++;
                //取模使指针循环
                currentPointer = (++currentPointer) % count;
                pageList.add(new Page(new ArrayList<>(list), integer, true));
            } else {
                pageList.add(new Page(new ArrayList<>(list), integer, false));
            }
        }
        print("FIFO");
    }

    //CLOCK算法
    public void CLOCK() {
        for (Integer integer : requestList) {
            if (isMissingPage(integer)) {
                if (currentIsFull()) {
                    int target = findIndex();
                    list.set(target, integer);
                    //已访问
                    request[list.indexOf(integer)] = true;
                    //指针移动，当前位置下一个
                    currentPointer = (list.indexOf(integer) + 1) % count;
                } else {
                    addPage(integer);
                    //已访问
                    request[list.indexOf(integer)] = true;
                    //指针移动，总数位置加1
                    currentPointer = (list.size()) % count;
                }
                sumMiss++;
                pageList.add(new Page(new ArrayList<>(list), request.clone(), integer, true));
            } else {
                //已访问
                request[list.indexOf(integer)] = true;
                pageList.add(new Page(new ArrayList<>(list), request.clone(), integer, false));
                //指针移动,指向当前
                currentPointer = list.indexOf(integer);
            }
        }
        print("CLOCK");
    }

    public void print(String option) {
        System.out.printf("     您选择了%s算法，执行结果如下：\n", option);
        System.out.println("访问页面\t物理块\t缺页中断");
        for (Page page : pageList) {
            if (Objects.equals(option, "CLOCK")) {
                System.out.printf("%d\t%s\t%s\t\n", page.getCurrent(), page.getList(), page.isInterrupt());
            } else
                System.out.printf("%d\t%s\t%s\t\n", page.getCurrent(), page, page.isInterrupt());
        }
        System.out.printf("""
                。。。。。。
                页面访问序列总长%d，%s算法共发生缺页中断%d次，缺页率为%d/%d。
                """, requestList.size(), option, sumMiss, sumMiss, requestList.size());
    }
}
